/**
 * 
 */
package edu.umd.clip.lm.util;

import java.util.*;

/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class RingBuffer<T> extends AbstractQueue<T> implements Cloneable {
	T[] buffer;
	int head; // the position of the first element
	int tail;  // the position after the last element
	int size;

	@SuppressWarnings("unchecked")
	public RingBuffer(int size) {
		buffer = (T[]) new Object[size]; 
		this.size = 0;
		head = size;
		tail = 0;
	}
	
	public RingBuffer(T[] buffer) {
		this(buffer, buffer.length);
	}
	
	public RingBuffer(T[] buf, int size) {
		this.buffer = buf;
		this.size = buf.length;
		this.head = 0;
		if (buf.length != size) {
			buffer = Arrays.copyOf(buf, size);
		}
		tail = buf.length;
		if (tail == buffer.length) {
			tail = 0;
		}
		checkInvariants();
	}

	RingBuffer() {
		
	}
	
	@SuppressWarnings("unchecked")
	public boolean setSize(int newSize) {
		if (newSize < size) return false;
		
		T[] newBuffer = (T[]) new Object[newSize]; 
		if (size == 0) {
			head = newSize;
			tail = 0;
		} else 	if (head < tail || tail == 0) {
			System.arraycopy(buffer, head, newBuffer, 0, size);
			head = 0;
			tail = size;
			if (tail == newSize) {
				tail = 0;
			}
		} else {
			System.arraycopy(buffer, head, newBuffer, 0, buffer.length - head);
			System.arraycopy(buffer, 0, newBuffer, buffer.length - head, tail);
			head = 0;
			tail = size;
		}
		buffer = newBuffer;
		return true;
	}
	/* (non-Javadoc)
	 * @see java.util.AbstractCollection#iterator()
	 */
	@Override
	public Iterator<T> iterator() {
		return new RingBufferIterator();
	}

	/* (non-Javadoc)
	 * @see java.util.AbstractCollection#size()
	 */
	@Override
	public int size() {
		return size;
	}

	/* (non-Javadoc)
	 * @see java.util.Queue#offer(java.lang.Object)
	 */
	@Override
	public boolean offer(T e) {
		checkInvariants();
		if (size < buffer.length) {
			/*
			if (head == 19 && e.toString().equals("667285at21")) {
				System.out.println();
			}
			*/
			putElement(e);
			checkInvariants();
			return true;
		}
		return false;
	}

	protected void putElement(T e) {
		checkInvariants();
		buffer[tail] = e;
		if (++tail == buffer.length) {
			tail = 0;
		}
		++size;
		checkInvariants();
	}
	
	public boolean isEmpty() {
		checkInvariants();
		return size == 0;
	}
	
	public boolean isFull() {
		checkInvariants();
		return size == buffer.length;
	}
	
	public T peekLast() {
		checkInvariants();
		if (size == 0) return null;
		int pos = tail == 0 ? buffer.length : tail;
		return buffer[pos-1];
	}
	
	public T pollLast() {
		checkInvariants();
		if (size == 0) return null;
		--size;
		if (tail == 0) tail = buffer.length;
		T e = buffer[--tail];
		checkInvariants();
		return e;
	}
	
	/* (non-Javadoc)
	 * @see java.util.Queue#peek()
	 */
	@Override
	public T peek() {
		checkInvariants();
		if (size > 0) {
			return buffer[head];
		}
		return null;
	}

	/* (non-Javadoc)
	 * @see java.util.Queue#poll()
	 */
	@Override
	public T poll() {
		checkInvariants();
		if (size == 0) return null;
		T e = buffer[head];
		if (++head == buffer.length) {
			head = 0;
		}
		--size;
		return e;
	}

	private class RingBufferIterator implements Iterator<T> {
		private int pos;
		
		private RingBufferIterator() {
			if (size > 0) pos = head;
			else pos = -1;
		}
		
		/* (non-Javadoc)
		 * @see java.util.Iterator#hasNext()
		 */
		@Override
		public boolean hasNext() {
			return pos > -1;
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		@Override
		public T next() {
			checkInvariants();
			if (pos < 0) throw new NoSuchElementException();
			T e = buffer[pos];
			if (++pos == buffer.length) {
				pos = 0;
			}
			if (pos == tail) pos = -1;
			return e;
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#remove()
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		Iterator<T> it = iterator();
		if (it.hasNext()) {
			sb.append(it.next().toString());
		}
		while(it.hasNext()) {
			sb.append(',');
			sb.append(it.next().toString());
		}
		sb.append(']');
		return sb.toString();
	}

	@Override
	public void clear() {
		size = 0;
		head = buffer.length;
		tail = 0;
	}
	
	protected void copyTo(RingBuffer<T> copy) {
		copy.buffer = Arrays.copyOf(buffer, buffer.length);
		copy.head = head;
		copy.tail = tail;
		copy.size = size;		
	}
	
	@Override
	public Object clone() {
		RingBuffer<T> copy = new RingBuffer<T>();
		copyTo(copy);
		return copy;
	}

	protected void checkInvariants() {
		if (true) return;
		
		int diff = tail - head;
		if (diff < 0) {
			diff += buffer.length;
		}
		
		if (diff != size && !(size == buffer.length && diff == 0)) {
			throw new IllegalStateException(String.format("Invalid ring buffer: head=%d, tail=%d, size=%d, length=%d", 
					head, tail, size, buffer.length));
		}
		
		if (size > 0) {
			if (tail > head) {
				for(int i=head; i<tail; ++i) {
					if (buffer[i] == null) {
						throw new IllegalStateException("null elements " + i);
					}
				}
			} else {
				for(int i=head; i<buffer.length; ++i) {
					if (buffer[i] == null) {
						throw new IllegalStateException("null elements " + i);
					}
				}
				for(int i=0; i<tail; ++i) {
					if (buffer[i] == null) {
						throw new IllegalStateException("null elements " + i);
					}
				}
			}
		}
	}
}
